perm filename LISP1.OLD[LSP,JRA]9 blob sn#115462 filedate 1974-08-08 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00017 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.SEC (LISP - a high-level mathematical language for data structures,Introduction)
C00007 00003	.REQUIRE "NOTES.INT" SOURCE_FILE
C00009 00004	.Sec(Symbolic expressions,Symbolic expressions)
C00016 00005	.<<Examples: s-exprs not sexprs>>
C00019 00006	.GROUP
C00020 00007	.REQUIRE "PROB1.PUB" SOURCE_FILE
C00021 00008	.SS(Primitive Functions)
C00023 00009	We have two unary selector functions, %3car%* and %3cdr%*, for traversing binary trees.
C00030 00010	.SS(Conditional Expressions,conditional expression)
C00034 00011	%3
C00040 00012	Here's an intuitive description of such a function (predicate) named %3equal%*.
C00045 00013	.REQUIRE "PROB2.PUB" SOURCE_FILE
C00046 00014	.SS(List Notation,lists)
C00051 00015	.REQUIRE "PROB4.PUB" SOURCE_FILE
C00052 00016	.SS(%3list%* and %3null%*)
C00055 00017	.SS(A respite)
C00061 ENDMK
C⊗;
.SEC (LISP - a high-level mathematical language for data structures,Introduction)

.BEGIN INDENT 20,20;
"... it is important not to lose sight of the fact that there is a difference
between training and education.  If computer science is a fundamental discipline,
then university education in this field should emphasize enduring fundamental
principles rather than transient current technology."
.END
.BEGIN TURN ON"→";
→Peter Wegner, %3Three Computer Cultures%*
.END

Just as it is unnecessary to learn machine language to study numerical
algorithms, it is also unnecessary to learn machine language to understand
non-numerical processes.  The distinction we are making is between data
structures and ⊗→storage structures↔←.  That is, ⊗→data structures↔← are independent
of %6how%* they are implemented on a machine.  Data structures are representations
of information chosen to exhibit certain ordering and accessibility relationships
between data items.  Certainly in the real world you cannot ignore
storage structures when you are deciding upon the data structures which
will encode your problem, but the interesting aspects of representation of
information can be discussed at the level of data structures with no loss
of generality.  The mapping of data structures to storage structures is
machine dependent anyway, and consists of bit-pushing, trickery and black
magic.  We are more interested in ideas than coding tricks.

A very crucial problem in data structures and algorithms is the
interplay between the representation and the algorithm:  if you pick a
frugal representation perhaps your accessing algorithms become more time
consuming or the algorithms become less general.  We will study this
interrelation carefully in this text. We will also see that it is possible,
and most beneficial, to structure our programs such that there is a very
clean interface between the abstract algorithm and the chosen representation.
That is, there will be a set of representation-manipulating programs to test,
select or construct elements of the domain; and there will be a program
encoding the algorithm. To change representations only requires changes
to constructors, selectors and predicates, not to the basic program.

.REQUIRE "NOTES.INT" SOURCE_FILE;

If you take a course in elementary number theory or better yet recursive
function theory, you would begin with a precise description of the domain
of interest (the non-negative integers perhaps, or 0 and the successor
function) and then describe the class of functions or operations which will
be allowed in the developing theory. We will do the same.
We will see other parallels between LISP and elementary number theory.
For example, the proof techniques used in LISP are generalizations  of those
of elementary number  theory.
Most important, there is the same subtle increase in  power of expression and
complexity. The simple beginnings of both theories lead rapidly to non-trivial
discussions. 
.Sec(Symbolic expressions,Symbolic expressions)
Our primitive domain consists of objects called ⊗→atoms↔← or ⊗→atomic symbols↔←.
Atoms contain the class usually called ⊗→literal atoms↔← and the class of signed integers; i.e.: 
.GROUP SKIP 2;
.BEGIN TABIT1(15);
.GROUP;
<atom>\:: = <literal atom>|<number>| -<number>
<literal atom>\:: = <atom letter>|<literal atom><atom letter>|<literal atom><digit>
<number>\:: = <digit>|<number><digit>
<atom letter>\:: =%3 A |B |C ...| Z%*
<digit>\:: = %30 |1 |2 ... |9%*
.APART;
.END;

.BEGIN TURN ON "#";
The above descriptions are called BNF (Backus-Naur Form) equations and are a style of
syntax specification common in Computer Science. The constitutents of 
such equations are:

the symbol "::=" to be read "is a ";

the symbol "|" to be read "or";

the non-terminal symbols:## the strings appearing to the left of the symbol ":="
⊗↓These strings conventionally begin with "<" and end with ">".←; 

the terminal symbols - those character strings appearing on the right hand side of a 
BNF equation and which are not non-terminals.

Though the left  hand side of each equation is restricted to be a single nonterminal
the right hand side may contain juxtaposed terminals and/or nonterminals. Such juxtaposition
is to be read "#followed#by".

Thus our first equation can be read `an <atom> is a <literal#atom> or a 
<number> or a "-" followed by a <number>'. The equations are interpreted as rewriting 
rules or generating rules, specifying how to construct new strings of terminals and
nonterminals from an existing string. We are particularly interested in terminal strings
generated from a single nonterminal; let %3x%* be a particular nonterminal symbol and
let %3G%* ⊗↓%3G%*: for grammar.← be a set of BNF equations then L(%3G,x%*) is called the 
%2language%* generated from %3x%* over %3G%* and consists of all terminal strings
generable by applying BNF rules from %3G%* first to %3x%*, and then to all resulting
sets of strings. Thus for our %3G%*, L(%3G%*,<literal#atom>) is 
the set of all strings consisting of digits and
upper-case letters subject to the restriction that the %2first%* character be a letter.
.END

.GROUP SKIP 2;
.BEGIN TABIT2(20,35);GROUP;
For example:\atoms\not atoms
%3\ABC123\2a
\12\a
\A4D6\$$g
\NIL\ABD.
\T\(A . B)
%*
.group skip 1;
.END;

Most of our discussions will deal with non-numeric atoms. From the point
of view of data structure, ⊗→numbers↔← are not very interesting. Most implementations
of LISP do however contain a large arithmetic entourage, including 
floating point numbers and operations. Many implementations also
give a wider class of literal atoms, allowing some special characters to appear;
for most of our discussion the above class is quite sufficient.

Using an operator to be described later, we are able to enlarge on
this primitive domain obtaining the domain of interest for LISP functions,
that is the class of %6⊗→symbolic expressions↔←%* or %6⊗→S-expressions↔←%* or also called
%6⊗→S-exprs↔←%*.  S-exprs include as a proper subset the atoms, but S-exprs can be
constructed of other S-exprs as follows:  a left-paren followed by an
S-expr, followed by a period, followed by an S-expr,
followed by a right-paren is also an S-expr.
Non-atomic sexpressions are also called %2⊗→dotted-pairs↔←%*.
Here's a BNF description of S-expressions.
.BEGIN TURN ON "←";
.P47:

←<sexpr> :: = <atom>|%3(%*<sexpr> . <sexpr>%3)

.END;

Notice that if we allow floating point numbers  as atoms some care needs to be
exercised when writing sexpressions. How should %3(A.1.2)%* be interpreted.
Is it the dotted pair %3(A . 1.2)%*, or is it just an ill-formed expression?
Evaluation of such ambiguous constructs will depend on the implementation; such
details do not interest us yet.
.<<Examples: s-exprs not sexprs>>
.BEGIN TABIT2(20,40);
.GROUP;
Examples:\S-exprs\not S-exprs
%3
\A\A . B
\(A . B)\(A . B . C)
\(((A.B) .C) . (A.B))\((A . B)))
%*
.APART;
.END;
.SS(Binary trees)
S-exprs have a natural
interpretation as %6⊗→binary trees↔←%*.  A binary tree is a branching structure 
consisting of a single root node and perhaps a collection of terminal
and non-terminal nodes.  From non-terminal nodes we sprout exactly two
branches; no branches are grown from the terminal nodes.  And most
important:  there are no intersecting branches.  We will talk about more
general structures later (called list-structures or directed graphs).
In our discussions, an <atom> will be attached to each terminal node, and
non-terminal nodes will be unlabeled.
.GROUP SKIP 1;
.GROUP;
Here are some binary trees:

.BEGIN TABIT2(5,40);SELECT 3;

					.		   
.GROUP SKIP 8;
\1    2       A   D   E\A    B    NIL

.END


.APART;
%1
Perhaps you can see how to interpret S-exprs now.  The atoms are
interpreted as terminal nodes;  and since non-atomic S-exprs always
have two sub-expressions we can write the first
sub-expression as the left branch of a binary tree and the second sub-
expression as the right branch.  
.GROUP SKIP 2;
.GROUP;
For example:

.BEGIN TABIT2(10,40);SELECT 3;

\(A . B)\(A . (B . C))
.GROUP SKIP 5;
\A   B\A    B    C

.APART;


.GROUP;
%1or:%*

\((A . B) . C)\(A . (B . NIL))

.GROUP SKIP 8;
\A     B         C\ A     B     NIL
.APART;
.END
%1
Other representations of binary trees which will be more suggestive when
we talk about implementation of LISP are:
%3
.GROUP
.BEGIN NOFILL;




(A .(B . C)) %1is:%*       A                                %1or%*    A            B         C



                              B    C



.END;
.APART
.SELECT 1;
.REQUIRE "PROB1.PUB" SOURCE_FILE;
.SS(Primitive Functions)
%1
So much for the domain of objects;  what we need now are some functions
or operators to perform operations on the domain.  
What is a function? The logician, Alonzo Church, says a function is simply a
mapping such that for any given argument in the domain of the function there
exists a corresponding value. No rule of computation need be given to help
locate values. However, as you might expect, rules of computation will be
an important part of our discussion and noting the differences between the
mathematical or logical concept of function and the related idea of 
procedure or computable function will be one of our interests.

The first LISP function we consider is the
⊗→%3cons%*↔← (construct) function which is used to generate s-exprs from less
complicated s-exprs.  %3cons%* is a ⊗→total function↔←, that is it is defined for all
sexpr arguments. It is a function of two arguments and has as value a
new sexpr interpreted as a binary tree with left branch as the first argument
and with right branch, the second argument.  For example:
 
.BEGIN CENTERIT;
←%3cons[A; B] = (A . B)

←cons[(A . B); C] = ((A . B) .C)
.END;
%1

.GROUP SKIP 1;
We have two unary selector functions, %3car%* and %3cdr%*, for traversing binary trees.
They are both ⊗→partial functions↔←;
that is, they are functions which are %2⊗→undefined↔←%* for some arguments.
⊗↓How "undefined" manifests itself on  a machine will depend on the implementation.
Sometimes error messages are given; sometimes it results in an excursion into
the subconscious. Shortly ({yonss(P85)}) we will show that a precise discussion
of partial functions and the "undefined" value can be given.←
These LISP functions are defined only for non-atomic arguments.
⊗→%3car%*↔← returns as value the first subexpression of its (composite) argument; ⊗→%3cdr%*↔← 
(pronounced could-er) returns as value the second sub-expression of its
argument.  For example:
.GROUP SKIP 1;
.BEGIN CENTERIT;
.GROUP;
←%3car[(A . B)] = A        car[A] %*is undefined.
←%3cdr[(A . B)] = B       cdr[(A . (B . C))] = (B . C)
←car[((A . B) . C)] = (A . B)
%*
.APART;
.END;
.GROUP SKIP 1;
.GROUP;
As with most mathematical theories, we will allow ⊗→functional composition↔←.
.GROUP SKIP 1;
.BEGIN CENTERIT;
%3
←car[cdr[(A . (B . C))]] = car[(B . C)] =  B 
←cdr[cdr[(A . (C . B))]] = cdr[(C . B)] =  B
←car[cons[x;y]] = x     cdr[cons[x;y]] = y .
%*
.END;
.APART

Notice that in the last two examples we have introduced variables (over
S-exprs).  In the sequel lower-case letters (or lower-case identifiers) will be
used freely as  variables.  So for example %3Y%* is an atom; %3y%* is a variable.

.BEGIN TURN ON "#";
Mathematically speaking, a composition of functions is simply another function
--#i.e.,#a mapping#-- and therefore nothing need be said about how to compute
composed functions. From a more pragmatic view, we can express evaluation
of expressions involving composed functions in terms of the evaluation of
subexpressions.
Perhaps the most natural way to evaluate expressions involving compositions is
to evaluate the inner-most expressions first, then work outwards. Arguments to
functions may be evaluated in any order. Thus:
.END

.BEGIN SELECT 3;GROUP;CENTERIT;

←cons[car[(A . B)];cdr[(A . (1 . 2))]] = cons[A;cdr[(A . (1 . 2))]] = cons[A;(1 . 2)] = (A .(1 . 2))
←%1or:%*  = cons[car[(A . B)];(1 . 2)] = cons[A;(1 . 2)] = (A .(1 . 2))
.END

This seems to be quite a simple operation but we shall soon see that evaluation
is a very complex process.

The composition of many %3car%* and %3cdr%* functions occurs so frequently that an
abbreviation has been developed.  
.BEGIN CENTERIT;DOUBLE SPACE;
.GROUP;
For example:
%3
←cadr[x] <= car[cdr[x]]
←caddr[x] <= car[cdr[cdr[x]]]
←cdar[x] <= cdr[car[x]]
%*
.END;
These compositions are also called ⊗→%3car-cdr-%2chains%1↔←, and are useful in
traversing binary trees. The "<="- notation is to be read "is defined to be the 
function ..."
This notation is only a temporary convenience and not part of LISP.
Very soon we will study what is involved in giving and using definitions in LISP
({yonss(P49)}).
For the moment intuition should suffice.

The syntax of the LISP expressions (or forms) allowed so far is given below.

.BEGIN TABIT1(13);GROUP;
.P66:

<form>\::= <constant> | <function>[<arg>; ... <arg>] | <function>[] | <variable>

<constant>\::= <sexpr>               (see {yon(P47)}.)

<function>\::= <identifier>

<arg>\::= <form>

<variable>\::= <identifier>

<identifier>\::= <letter> | <identifier><letter> | <identifier><digit>

<letter>\::= %3a | b | ... | z  

.END
We will frequently violate these syntax equations, allowing function names
containing special characters, e.g. %3fact*%*, %3fib%41%1 or + ; or writing %3x +y%*
instead of %3+[x;y]%*.  Rather than attempt to characterize these violations,
occurrences of such should be clear from context.

Notice that the class <⊗→form↔←> is a collection of LISP expressions which can
be evaluated; either constants, function name followed by arguments, or a 
variable which should have a current binding or value. Again we will wait
to {yonss(P49)} for a precise description.

An important restraint on LISP forms which is not covered by the syntax
equations is the requirement that functions are defined as being n-ary for
some %2fixed%* n. n-ary functions
must have %2exactly%* n arguments presented to them whenever they are applied.
.P95:
Thus %3cons[A], cons[A;B;C], %*and %3car[A;B]%* are all ill-formed expressions
and are therefore undefined.
.SS(Conditional Expressions,conditional expression)
We cannot generate a very exciting theory based simply on %3car, cdr,%* and %3cons
%*
with functional composition. Before we can write reasonably interesting 
algorithms we must have some way of performing conditional actions.
To do this we need ⊗→predicates↔←. A LISP predicate will simply be a function
returning a value representing truth or falsity.  Since our functions
return Sexprs as values we must represent truth and falsity as Sexprs.
We will take the atoms ⊗→%3T%*↔← and ⊗→%3NIL%*↔← to represent ⊗→true↔← and ⊗→false↔←, respectively.
Notice that since LISP predicates %2are%* functions, they may be freely 
composed with other functions.

LISP has two primitive predicates.
The first is a total predicate named ⊗→%3atom%*↔←.  It is a predicate
of one argument, returning %3T%* or %3NIL%* depending on whether or not the value of that
argument is atomic.
.GROUP SKIP 1;
.BEGIN CENTERIT;
.GROUP
%3
←atom[A] = atom[NIL] = T
←atom[atom[A]] = T = atom[atom[(A . B)]]
%*
.APART
.END

The second primitive predicate is named ⊗→%3eq%*↔←.  It is a binary predicate, defined
only if its arguments are both atomic.  It returns %3T%* if the arguments evaluate to the
same atom; it returns %3NIL%* otherwise.
.BEGIN CENTERIT;
%3
.GROUP SKIP 1;
.GROUP
←eq [A;A] = T			eq [A;B] = NIL
←eq [(A . B); A] %* is undefined, as is    %3eq [(A . B);(A . B)]
←eq [eq [A;B];eq [C;D]] = T
%*
.APART;
.END

The IF-THEN-ELSE operation in LISP is called the conditional expression.  It
is written:
.BEGIN CENTERIT;
%3
←[p%41%* → e%41%*; p%42%* → e%42%*  ... ; p%4n%*  → e%4n%*]
%1
.END

.P40:
The meaning (or semantics) of conditionals is:  Each %3p%4i%1 is a predicate; 
each %3e%4i%1
is an expression.  We evaluate the %3p%4i%1 's from left to right, finding the %2first
%*
which returns value %3T%*.  When we find such a %3p%4i%1 , we evaluate the corresponding
%3e%4i%1.  The value of the conditional expression is the value computed by %3e%4i%1; if none
of the %3p%4i%1's are true then the conditional expression is undefined.  The
conditional expression is also undefined if we come across a %3p%4i%1
which is undefined.  
.BEGIN CENTERIT;
.GROUP;
Examples:

%3
←[atom [A] → B; eq [A;(A . B)] → C] = B
←[eq [A;(A . B)] → C; atom [A] → B] is undefined
←[atom [(A . B)] → B; eq [A ; B] → C; eq [car[(A . B)]; cdr[(B . A)]] → E] = E
%1
.APART
.END
Notice that the p%42%* expression of the first example is undefined, but
the conditional gives value %3B%* since p%41%* gives value %3T%*.


In applications of conditional expressions it is often convenient to be
assured that the conditional always is defined.  To make sure that at least one of
the %3p%4i%1's is true we can pick a predicate for %3p%4n%1, (the last predicate in the 
conditional) which is always true.  You can think of lots of predicates which
are always true ( for example, %3eq [1;1]%* ).  A natural predicate is the
constant predicate, %3T%*.  Thus:
.GROUP

.BEGIN CENTERIT;

%3
←[p%41%*  → e%41%*; T → e%42%*]
%1
.END
can be read:  If %3p%41%1  is true then  %3e%41%1  else %3e%42%1.  (or otherwise %3e%42%1)

.APART;
.BEGIN TURN ON "#";
.P17:
Some care has to be given to the defintion of the meaning of a conditional expression.
First the order of evaluation %2is%* important. 
Consider: %3f[x;y]#<=#[y#=0#→#0;#T#→#x/y]%*. If we insisted on evaluating all of the
constitutients of the conditional first, then %3f[ ...;0]%* would be undefined, rather
than giving value %30%* as our current interpretation would.

There are other interpretations of equal merit. Consider the nonsense definition:
%3g[x;y]#<=#[lic[x]#→#1;T#→#1]%*. Clearly, assuming that %3lic%* is a total predicate, 
any value computed by %3g%* will be %31%*. But requiring  left-to-right evaluation
could spend a great deal of unnecessary computation if %3lic%* is a 
%2l%*ong %2i%*nvolved %2c%*alculation.

Questions of evaluation are non-trivial. You should at least be aware that some
decisions have been made and others were possible.
.P88:
With conditional expressions, we are seeing the first major step away from
traditional mathematical thought. We may not continue to think of conditional
expressions as a notational convenience for evaluation of some mathematical 
expression, say:
.BEGIN CENTERIT; SELECT 3;
←[p%41%* → e%41%*; p%42%* → e%42%*] %1is%3 cond[p%41%*; e%41%*; p%42%*; e%42%*]
.END
where %3cond%* is a function. There are several difficulties: 
certainly the order of evaluation cannot be adequately expressed but perhaps the
most serious involves the observation that arguments to %3cond%* would frequently
be undefined. Examine %3[eq[A;B]#→#C;#eq[car[A];B]#→#D]]%* and
%3cond[eq[A;B];C;eq[car[A];B];D]%*. However, in {yonss(P85)} we will show that
a reasonable mathematical interpretation can be given to LISP conditional 
expressions.
.END

A word to the wise.  It doesn't seem like you can do much damage with such
a limited collection of operations.  %6Do not be deceived!%*  In elementary number
theory all you have is zero and some simple functions, and elementary number theory
is far from elementary.
Manipulation of our primitives, with composition, and conditional expressions, 
coupled with techniques for definition can %2also%* become complicated.

For example: our predicate %3eq%* is defined only for atomic arguments.  We would like
to be able to test for equality of arbitrary sexprs.  
By equality we mean: as trees, the sexprs have the same branching structure; and
the corresponding terminal nodes are labeled by the same atoms.
Thus, we would
like to define a predicate, ⊗→%3equal%*↔←, such that:
.GROUP SKIP 1;
.GROUP
.BEGIN CENTERIT;
%3
←equal [(A . B);(A . B)] = T = equal [A;A]
←equal [(A . B);(B . A)] = NIL 
←equal [(A . (B . C));(A . (B . C))] = T

%1
.END
.APART

Here's an intuitive description of such a function (predicate) named %3equal%*.

.BEGIN INDENT 0,4;
1.  If both arguments are atomic then see what %3eq%* says about them
(are they "%3eq%*").  We can test if they are both atomic by using %3atom%*
and a conditional expression.
.END

2.  If one is atomic and the other is not they can't be equal s-exprs.

.BEGIN INDENT 0,5;
3.  Otherwise both are non-atomic sexprs.  Both have two sub-expressions.
Look at both first subexpressions.  If the first sub-expressions are not
equal then certainly the initial expressions cannot hope to be equal.  
If, however, the first subexpressions are equal then the question of
whether or not the initial expressions are equal depends on the
equality (or non-equality) of the second subexpressions.  Thus the
following definition:
.END
%3
.GROUP SKIP 1;
.BEGIN TABIT2(19,30);GROUP;
.P1:
     equal[x;y] <=\[atom[x] → [atom[y] → eq [x;y];
\\ T→ NIL];
\ atom[y] → NIL;
\ equal [car[x];car[y]] → equal[cdr[x];cdr[y]];
\ T → NIL]

.END
%1
Notice that we use nested conditional expressions in %3equal%*; e%41%*
is itself a conditional. Also we have used predicates in the e%4i%* positions
at e%43%* and e%411%*; this is perfectly reasonable since %3equal%* is a predicate
and thus returns either %3NIL%* or %3T%*. 

Let's show that %3equal%* does perform correctly for a specific example.  This will
also show a complicated evaluation of a conditional expression.

.BEGIN TABIT2(25,44);GROUP;SELECT 3;

equal[(A . B);(A . C)] =\[atom[(A . B)] → [atom[(A . C)] → eq [(A . B);(A . C)];
\\ T→ NIL];
\ atom[(A . C)] → NIL;
\ equal [car[(A . B)];car[(A . C)]] → equal[cdr[(A . B)];cdr[(A . C)]];
\ T → NIL]
.APART
.BEGIN FILL;SELECT 1;
Now using the meaning of conditionals ({yon(P40)}),
we find that p%41%* (i.e.,#%3atom[(A#.#B)]%*#)
and p%42%* (#%3atom[(A#.#C)]%*#) when evaluated (in order) give %3NIL%*.
We must now evaluate p%43%*: %3equal[car[(A#.#B)];car[(A#.#C)]]%*.
This reduces to %3equal[A;A]%*, and:
.END

.GROUP;
   equal[A;A] =\[atom[A] → [atom[A] → eq[A;A];
\\ T→ NIL];
\ atom[A] → NIL;
\ equal [car[A];car[A]] → equal[cdr[A];cdr[A]];
\ T → NIL]
.APART
.BEGIN FILL;SELECT 1;
This conditional expression will finally evaluate to %3T%*. So p%43%* in the
original call of %3equal[(A#.#B);(A#.#C)]%* is true, and we are faced with the evaluation of e%43%*
which is %3equal[cdr[(A#.#B);cdr(A#.#C)]]%*. After evaluation of the arguments and 
evaluation of the conditional expression defining %3equal%* we will finally
return value %3NIL%*. That is %3(A . B)%* and %3(A . C)%* are %2not%* equal.
Clearly evaluation of LISP expressions in this great detail is not a process
which we wish to do very often. 

Notice that throughout this example expressions like %3atom[(A#.#B)]%*
or %3eq[(A#.#B);(A#.#C)]%* were appearing but were never evaluated because
of the way in which we defined evaluation of conditionals.
.END
.END
Finally, to include conditional expressions in our syntax of LISP
expressions, we should add:

.BEGIN TABIT1(11);

<form>\::= [<form> → <form>; ... <form> → <form>]         (see {yon(P66)})

.END

.REQUIRE "PROB2.PUB" SOURCE_FILE;
.REQUIRE "PROB3.PUB" SOURCE_FILE;

.SS(List Notation,lists)
.BEGIN TURN ON "#";
In many applications of LISP it will be very convenient to represent
sequences.  E.g. %3(x%41%*, x%42%*, x%43%*)%1.  We will allow sequences to have
sub-sequences (to an arbitrary depth) e.g. %3(A,#(B,#C),#D,#(E,#B))%*.  The obvious
question is how to represent sequences as Sexprs.  Since sequences can be of
arbitrary length any representation must include an unambiguous way of
determining the end of such a sequence.
.END
.GROUP
The choice we make is represented graphically as follows:
%3
.BEGIN VERBATIM


(X, Y, Z)  ≡                                                      ≡ (X  . (Y  . (Z  . NIL)))  

                  X               Y               Z      NIL

.END
.APART
%1
Or:
.GROUP SKIP 6;
.BEGIN VERBATIM;SELECT 3;
                 X           Y          Z          NIL
.END

That is the right-hand branch in any binary tree representing a sequence
will always point to the rest of the sequence or will be the atom %3NIL%*.  It
is not by accident that the atom %3NIL%* is used both for falsity and the termination
symbol for sequences.  You should become fluent in translating between
sexpr-notation and sequence notation.

In more standard terminology sequences are called lists, thus we
will refer usually to ⊗→list-notation↔←, list terminator, etc.  You should also
become fluent in applying our basic functions to lists without having to
translate back to sexpr-notation.

Notice that the %3car-cdr%*-chains are very useful for obtaining elements of a list.
To retrieve the n%8th%* element of a list use %3cad%8n-1%*r.
%1

A final point:  what about the empty sequence or empty list? Looking at the
graphical interpretation of a sequence it appears natural to take ⊗→%3NIL%*↔← as
the ⊗→empty list↔← since after you have removed all the elements from the list,
%3NIL%*, the list terminator is all that is left.  Also from the standpoint of
sequence notation, the empty sequence is represented as:  "⊗→%3( )%*↔←".  To be
consistent, then, we will define %3( )%* to be the same as the atom %3NIL%*.  And
a notational point:  in graphical notation it is often convenient to write
.GROUP
.BEGIN TABIT2(10,30);

\\as                  .  

\       %3NIL%*
.END
.APART
%1
.BEGIN TURN ON "←";TABIT3(20,30,40);
.GROUP
Thus, for example:

←%3(A, (B, C), D)%* is:



%3
\A\\    D



\\   B\   C

%1
or:
%3

←A








←B    C    NIL     D          NIL 
%1
.END
.APART
Finally, in list-notation the commas can be replaced by spaces.
.BEGIN CENTERIT;
%3
←e.g. (A, (B, C), D) ≡ (A(B C)D).
%1
.END
Note:  the "dots" in dot-notation are %2never%* optional.


.REQUIRE "PROB4.PUB" SOURCE_FILE;
.SS(%3list%* and %3null%*)
.BEGIN TURN ON "←";
We deal with functions restricted to lists frequently enough that
it is reasonable to define the list counterpart to %3atom%*, that is
a predicate which asks,
"is the list empty?".  The predicate used for testing for the empty list
is called ⊗→%3null%*↔← and can be defined as:

←%3null[x] <= [atom[x] → eq[x;NIL]; T → NIL].%1

Similarly, it is convenient to have a notation representing the construction
of a list from an arbitrary number of sexpressions ⊗↓Some people
restrict lists so that elements of a list are either atomic or are lists themselves.
We shall not do so. Elements of a list may be arbitrary sexprs.←.

⊗→%3list%*↔←%3[%1x%41%1; x%42%*; ... x%4n%*] generates a list consisting of the values
of the n arguments. That is, the effect is:

←%3cons[%1x%41%3;cons[%1x%42%3; ... cons[%1x%4n%3;NIL]] ...] %1.

.BEGIN GROUP;NOFILL;
Examples:
.select 3;
←list[A;B] = (A B)
←list[A;B;C] = (A B C)
←list[cons[A;B];car[(A . B)]] = ((A . B) A)
←list[A;list[B;C]] = list[A;(B C)] = (A (B C))
←list[] = NIL
←list[NIL] = (NIL)
.END

Notice that %3list%* is %2not%* a function; it %2does%* evaluate its arguments,
but it can take an arbitrary number of them.
For the moment, %3list%* is simply a notational abbreviation for the nested %3cons%*.
.END

.SS(A respite)
.BEGIN TURN ON "←";
This section contains some hints and notes on the introductory material of
this chapter. First a reiteration of the previous admonition: though
this material seems quite straightforward, the next chapter will begin
to show you that things are not all that trivial.  LISP is quite powerful.
The preceeding material %2is%* basic and the sooner it becomes second nature
to you the better.  

Perhaps many of these hints you have discovered yourself.

In graphing `list notation' first discover how many elements are in the list.
This can be done simply by counting parentheses. Then draw the spine of a 
tree which will have as many  left branches as there are elements.  The right
branch %2always%* ends with %3NIL%*. Then examine the structure of each node.
Notice again that to find the n%8th%* element in a list, use %3cad%8n-1%*r%1.
Thus %3cdr%* is %2never%* the second element of a list. %3cadr%* is the second
element, %3cdr%* is the %2rest%* of the list.

When evaluating or writing functions or (predicates) %2always%* keep in mind
any  restrictions of the function:  is it partial, is it total, defined only
for lists, are there restrictions on arguments; when taking %3car%* or %3cdr%* is the
argument non-atomic.

A few tricks were embedded in the problem sets.
In {yonss(P11)}, recall problem %28%*. The composition %3atom[cons[ ...]]%*
will always evaluate to %3NIL%* since the result of %3cons%*-ing is always
non-atomic.
In %210.%*, we used identifiers with  the same
letter strings as predicate names, %3ATOM%* and %3EQ%*. %3ATOM%* and %3EQ%*
are perfectly good identifiers, and are %2not%* the LISP predicates.
%214.%* shows that predicates are perfectly good expressions to evaluate; e%41%*
is a predicate. Similarly, in %216.%*, conditional expressions may appear within
functional composition.

.BEGIN TURN ON "#";
Notice that %3twist%* in II is total whereas %3findem%* is partial.
%3findem%* is partial since %3y%* must be atomic. Both functions build 
new trees, %3twistem%* reverses left- and right-branches recursively;
%3findem%* builds a tree with the same branching structure as %3x%*,
but the terminal nodes contain %3T%* at the points where the atom %3y%*
appears in the original tree, and %3NIL%* otherwise.
.P24:
Perhaps you also noticed in %3findem%* that the construction: %3atom[x]#→#eq[x;y]%*
could have been used instead of %3atom[x]#→#[eq[x;y]#→#T;#T#→#NIL]%*. Prove it.
.END

In {yonss(P12)} you should have discovered that the value of:

←%3cons[%1x%41%3,(%1x%42%*, ...x%4n%3)]%1 is: %3(%1x%41%*, x%42%*, ... x%4n%3).

%1Notice that %3list[%1x%41%3;(%1x%42%*, ... x%4n%3)]%1 is 
%3(%1x%41%3 (%1x%42%* ... x%4n%3))%1.
So %3cons%* will add a new element to the front of an existing list. %3list%*
will create a new list whose elements will be the values of the arguments
to %3list%*.

Be clear on the difference between the empty list, %3NIL%*, and 
the list consisting of %3NIL%*, %3(NIL)%*. %3(NIL)%* is 
an abbreviation for %3(NIL . NIL)%*, which certainly is not %3NIL%*.
List notation is always an abbreviation and can always be translated back
into a sexpr.

.END